package com.leetcode.dfs;

public class Leetcode494 {
    private int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        dfs(0, 0, nums, target);
        return count;
    }

    private void dfs(int sum, int index, int[] nums, int target) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        dfs(sum + nums[index], index + 1, nums, target);
        dfs(sum - nums[index], index + 1, nums, target);
    }
}
